#include <bits/stdc++.h>

using namespace std;

// 删除至少几个字符可以变成另一个字符串的子串
// 给定两个字符串s1和s2
// 返回s1至少删除多少字符可以成为s2的子串
// 对数器验证

// 生成s1字符串的所有子序列串
void f(string& s1, int i, string path, vector<string>& v)
{
    if(i == s1.size())
    {
        v.emplace_back(path);
        return;
    }
    f(s1, i + 1, path, v);
    f(s1, i + 1, path + s1[i], v);
}

// 暴力方法
// 为了验证
int minDelete1(string& s1, string& s2)
{
    vector<string> v;
    f(s1, 0, "", v);
    // 排序 : 长度大的子序列先考虑
    // 因为如果长度大的子序列是s2的子串
    // 那么需要删掉的字符数量 = s1的长度 - s1子序列长度
    // 子序列长度越大，需要删掉的字符数量就越少
    // 所以长度大的子序列先考虑
    sort(v.begin(), v.end(), [](auto& a, auto& b){
        return a.size() > b.size();
    });

    for(auto& str : v)
    {
        // 检查s2中，是否包含当前的s1子序列str
        if(s2.find(str) != string::npos)
        {
            return s1.size() - str.size();
        }
    }
    return s1.size(); // 将 s1 的全部字符删掉成为空串
}

// 正式方法，动态规划
// 已经展示太多次从递归到动态规划了
// 直接写动态规划吧
int minDelete2(string& s1, string& s2)
{
    int m = s1.size(), n = s2.size();
    // dp[i][j] : s1[前缀长度为i]至少删除多少字符，可以变成s2[前缀长度为j]的任意后缀串
    vector<vector<int>> dp(m + 1, vector<int>(n + 1));
    for(int i = 1; i <= m; ++i)
    {
        dp[i][0] = i;
        for(int j = 1; j <= n; ++j)
        {
            if(s1[i - 1] == s2[j - 1])
            {
                // 不需要删除字符
                dp[i][j] = dp[i - 1][j - 1];
            }
            else
            {
                // 删除 i 字符
                dp[i][j] = dp[i - 1][j] + 1;
            }
        }
    }

    int ans = INT_MAX;
    for(int j = 0; j <= n; ++j) ans = min(ans, dp[m][j]);
    return ans;
}

int minDelete3(string& s1, string& s2)
{
    int m = s1.size(), n = s2.size();
    int dp[n + 1]{};
    for(int i = 1; i <= m; ++i)
    {
        dp[0] = i;
        for(int j = 1, leftUp = i - 1, backup; j <= n; ++j)
        {
            backup = dp[j];
            if(s1[i - 1] == s2[j - 1])
                dp[j] = leftUp;
            else
                ++dp[j];
            leftUp = backup;
        }
    }

    int ans = INT_MAX;
    for(int j = 0; j <= n; ++j) ans = min(ans, dp[j]);
    return ans;
}

// 为了验证
// 生成长度为n，有v种字符的随机字符串
string randomString(int n, int v)
{
    string ans;
    for(int i = 0; i < n; ++i)
    {
        ans += (char)('a' + rand() % v);
    }
    return ans;
}

// 为了验证
// 对数器
int main()
{
    srand(time(nullptr));
    // 测试的数据量比较小
    // 那是因为数据量大了，暴力方法过不了
    // 但是这个数据量足够说明正式方法是正确的
    int n = 12;
    int v = 3;
    int testTime = 20000;
    cout << "测试开始" << endl;

    for(int i = 0; i < testTime; ++i)
    {
        int len1 = rand() % n + 1;
        int len2 = rand() % n + 1;
        string s1 = randomString(len1, v);
        string s2 = randomString(len2, v);
        int ans1 = minDelete1(s1, s2);
        int ans2 = minDelete2(s1, s2);
        if(ans1 != ans2) cout << "出错了!" << endl;
    }

    cout << "测试结束" << endl;

    return 0;
}